package interview.getMaxSortDistance;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public class GetMaxSortDistance {

    public static int getMaxSortDistance(List<Integer> list){
        AtomicInteger max = new AtomicInteger(list.get(0));
        AtomicInteger min = new AtomicInteger(list.get(0));
        list.forEach(item -> {
            if(item >= max.get()) max.set(item);
            if(item <= min.get()) min.set(item);
        });
        //计算差值 创建桶需要的
        int different = max.get() - min.get();
        if (different == 0) return 0;
        //初始化桶
        int size = list.size();
        List<Bucket> buckets = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            buckets.add(new Bucket());
        }
        //遍历原数组 计算桶位置
        list.forEach(item -> {
            int index = ((item - min.get()) * (size - 1) / different);
            Bucket bucket = new Bucket();
            if (buckets.get(index).getMax() == 0 || buckets.get(index).getMax() < item) {
                bucket.setMax(item);
                buckets.set(index,bucket);
            }
            if (buckets.get(index).getMin() == 0 || buckets.get(index).getMin() > item) {
                bucket.setMin(item);
                buckets.set(index,bucket);
            }
        });
        //遍历桶集合 找到最大差值
        AtomicInteger atomicInteger = new AtomicInteger(0);
        AtomicInteger lastMax = new AtomicInteger(buckets.get(0).getMax());
        for (Bucket bucket : buckets) {
            if (bucket.getMin() == 0) continue;
            if (bucket.getMin() - lastMax.get() > atomicInteger.get()){
                atomicInteger.set(bucket.getMin() - lastMax.get());
            }
            lastMax.set(bucket.getMax());
        }
        return atomicInteger.get();
    }
}
